/**
 * https://leetcode-cn.com/problems/missing-number/
 * 丢失的数字
 * @param nums 
 */
const missingNumber = (nums: number[]): number => {
    const len = nums.length;
    // 默认缺失的是最后一个
    let miss = len;

    // 两个一样的数进行异或得到为0
    for (let i = 0; i < len; i++) {
        miss ^= (i ^ nums[i])
    }

    return miss

};



const missingNumber4 = (nums: number[]): number => {
    const len = nums.length;

    // 求出[0, len]的和 - nums的和相减

    // [0, len]
    const total = (len * (len + 1)) >> 1

    // nums和
    let sub = 0
    for (let n of nums) sub += n

    // 找不到
    return total - sub
};



const missingNumber3 = (nums: number[]): number => {
    const len = nums.length;

    const set = new Set<number>()

    // 放入set中
    for (let n of nums) set.add(n)

    for (let i = 0; i <= len; i++) {
        // 该项不在set中
        if (!set.has(i)) {
            return i
        }
    }

    // 找不到
    return -1
};



const missingNumber2 = (nums: number[]): number => {
    const len = nums.length;

    // 1. 排序
    nums.sort((a, b) => a - b)

    // 判断最后一项
    if (nums[len - 1] !== len) {
        return len
    }

    // 2. 遍历
    let v = nums[0]

    // 第一项不是0
    if (v !== 0) return 0


    for (let i = 1; i < len; i++) {
        if (nums[i] !== v + 1) {
            // 不相等, 返回
            return v + 1
        }
        v = nums[i]
    }

    // 不缺
    return -1
};  